Search results for "electronic design automation"
showing 10 items of 118 documents
A Novel Fault-Tolerant Routing Algorithm for Mesh-of-Tree Based Network-on-Chips
2019
Use of bus architecture based communication with increasing processing elements in System-on-Chip (SoC) leads to severe degradation of performance and speed of the system. This bottleneck is overcome with the introduction of Network-on-Chips (NoCs). NoCs assist in communication between cores on a single chip using router based packet switching technique. Due to miniaturization, NoCs like every Integrated circuit is prone to different kinds of faults which can be transient, intermittent or permanent. A fault in any one component of such a crucial network can degrade performance leaving other components non-usable. This paper presents a novel Fault-Tolerant routing Algorithm for Mesh-of-Tree …
Run-time scalable NoC for FPGA based virtualized IPs
2017
The integration of virtualized FPGA-based hardware accelerators in a cloud computing is progressing from time to time. As the FPGA has limited resources, the dynamic partial reconfiguration capability of the FPGA is considered to share resources among different virtualized IPs during runtime. On the other hand, the NoC is a promising solution for communication among virtualized FPGA-based IPs. However, not all the virtualized regions of the FPGA will be active all the time. When there is no demand for virtualized IPs, the virtualized regions are loaded with blank bitstreams to save power. However, keeping active the idle components of the NoC connecting with the idle virtualized regions is …
A Stochastic Routing Algorithm for Distributed IoT with Unreliable Wireless Links
2016
Punctual and reliable transmission of collected information is indispensable for many Internet of Things (IoT) applications. Such applications rely on IoT devices operating over wireless communication links which are intrinsically unreliable. Consequently to improve packet delivery success while reducing delivery delay is a challenging task for data transmission in the IoT. In this paper, we propose an improved distributed stochastic routing algorithm to increase packet delivery ratio and decrease delivery delay in IoT with unreliable communication links. We adopt the concept of absorbing Markov chain to model the network and evaluate the expected delivery ratio and expected delivery delay …
A strategic oscillation simheuristic for the Time Capacitated Arc Routing Problem with stochastic demands
2021
Abstract The Time Capacitated Arc Routing Problem (TCARP) extends the classical Capacitated Arc Routing Problem by considering time-based capacities instead of traditional loading capacities. In the TCARP, the costs associated with traversing and servicing arcs, as well as the vehicle’s capacity, are measured in time units. The increasing use of electric vehicles and unmanned aerial vehicles, which use batteries of limited duration, illustrates the importance of time-capacitated routing problems. In this paper, we consider the TCARP with stochastic demands, i.e.: the actual demands on each edge are random variables which specific values are only revealed once the vehicle traverses the arc. …
Game Theoretic Decentralized Feedback Controls in Markov Jump Processes
2017
This paper studies a decentralized routing problem over a network, using the paradigm of mean-field games with large number of players. Building on a state-space extension technique, we turn the problem into an optimal control one for each single player. The main contribution is an explicit expression of the optimal decentralized control which guarantees the convergence both to local and to global equilibrium points. Furthermore, we study the stability of the system also in the presence of a delay which we model using an hysteresis operator. As a result of the hysteresis, we prove existence of multiple equilibrium points and analyze convergence conditions. The stability of the system is ill…
The probabilistic pickup-and-delivery travelling salesman problem
2019
Abstract Transportation problems are essential in commercial logistics and have been widely studied in the literature during the last decades. Many of them consist in designing routes for vehicles to move commodities between locations. This article approaches a pickup-and-delivery single-vehicle routing problem where there is susceptibility to uncertainty in customer requests. The probability distributions of the requests are assumed to be known, and the objective is to design an a priori route with minimum expected length. The problem has already been approached in the literature, but through a heuristic method. This article proposes the first exact approach to the problem. Two mathematica…
A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem
2016
The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
2019
The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW hav…
Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks
2016
Abstract This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loaded and is operated in a last-in-first-out (LIFO) fashion, meaning that when an item is picked up, it is positioned at the rear of a stack. An item can only be delivered if it is in that position. This problem arises in the transportation of heavy or dangerous material where unnecessary handling should be avoided, such as in the transportation of cars between car dealers and the transportation of livestock from farms to slaughterhouses. To solve this problem, we propose two different branch-price-and-cut algorithms. The first sol…
The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints
2019
In classical routing problems, each customer is visited exactly once. By contrast, when allowing split deliveries, customers may be served through multiple visits. This potentially results in substantial savings in travel costs. Even if split deliveries are beneficial to the transport company, several visits may be undesirable on the customer side: At each visit the customer has to interrupt his primary activities and handle the goods receipt. The contribution of the present paper consists in a thorough analysis of the possibilities and limitations of split delivery distribution strategies. To this end, we investigate two different types of measures for limiting customer inconvenience (a m…